﻿namespace _70爬楼梯
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Solution solution = new Solution();
            Console.WriteLine(solution.ClimbStairs(10));
            Console.WriteLine(solution.ClimbStairs2(10));
        }
    }
    /// <summary>
    /// 
    /// </summary>
    public class Solution
    {
        public int ClimbStairs(int n)
        {
            if (n <= 1) return n;
            int p = 0, q = 0, r = 1;
            for (int i = 2; i <= n; ++i)
            {
                p = q;
                q = r;
                r = p + q;
            }
            return r;
        }
        int[] f = new int[110];
        public int ClimbStairs2(int n)
        {
            f[0] = f[1] = 1;
            if (n <= 1) return n;
            for (int i = 2; i <= n; ++i)
            {
                f[i] = (f[i - 1] + f[i - 2]);
            }
            return f[n];
        }
    }

}